/*
 * metric.c
 *
 *  Created on: 17 sept. 2013
 *      Author: the
 */
#include "metric.h"

//Look for a given neighbor (given its ID) in the N1 list.
//Return the N1 index if found and -1 otherwise
int getIndexN1(struct node aNode, int id)
{
	int i;

	for(i=0;i<aNode.nbN1;i++)
		if(aNode.N1[i].id==id) return(i);

	return(-1);
}

//Look for a radio number between two nodes, the struct node aNode and a neighbor with index id (the radio is set by the allocation algorithm)
int getRadioN1(struct node aNode, int id)
{
	int indice;

	//Chercher indice nextHop dans la liste du voisinage
	if( (indice=getIndexN1(aNode, id)) <0){
		fprintf(stderr,"getRadioN1(): erreur indice\n");
		exit(1);
	}
	//On recherche la radio au niveau du noeud
	return(aNode.N1[indice].radio);
}


//Check if node id uses the given frequency or not. Return -1 if not, otherwise return the index of interface using it.
int usedfreq(int id, int frequency)
{
    int j=0;
    for (j=0;j<nodes[id].nbOfRadios;j++)
    {
        if (nodes[id].frequency[j]==frequency) return j;
    }
    return -1;
}//End of the function usedfreq()

//Check if node i in N1 of node id uses the given frequency or not. Return -1 if not, otherwise return the index of interface using it.
int usedfreqN1(int id, int i, int frequency)
{
    int j=0, idNeighbor;

	if(i>=nodes[id].nbN1){
		fprintf(stderr,"Erreur usedfreqN1(): valeur du second argument incorrect\n");
		exit(1);
	}

	idNeighbor=nodes[id].N1[i].id;
	for (j=0;j<nodes[idNeighbor].nbOfRadios;j++)
	{
        	if (nodes[idNeighbor].frequency[j]==frequency) return j;
    	}
	return -1;
}//End of the function usedfreqN1()

//Return 1 if there is a route (in the routing table) from id1 to id2 (id2 is the next hop)
//return 0 otherwise
int linkIsActive(int id1, int id2)
{
	int i;

	for(i=0;i<nbOfRadios;i++)
	{
		if(nodes[id1].routingTable[i].nextHop==id2)
			return(1);
	}

	return(0);
}//End of the function linkIsActive()

//Return 1 if the frequency "frequency" is used between the nodes "id1" and "id2".
//Otherwise, returns 0.
int linkFrequency(int id1, int id2, int frequency)
{
    int j=0, condNode1=0, condNode2=0;

	//If they are not neighbors, we stop
	if(!isNeighbor(id1,id2)) return(0);

	//We test if "id1" uses "frequency"
	for (j=0;j<nodes[id1].nbOfRadios;j++)
        	if (nodes[id1].frequency[j]==frequency) condNode1=1;

	//We test if "id1" uses "frequency"
	for (j=0;j<nodes[id2].nbOfRadios;j++)
        	if (nodes[id2].frequency[j]==frequency) condNode2=1;

	return (condNode1*condNode2);
}//End of the function linkFrequency()

// Verifier que le noeud id1 et id2 utilisent la fréquence 'frequency' pour communication
// Si oui, retourner 1, par contre, retourner 0
int linkUsedFrequency(int id1, int id2, int frequency)
{
	 //If they are not neighbors, we stop
	if(!isNeighbor(id1,id2))
		return(0);

	// get index of id2
	int idVetex2 = getIndexN1(nodes[id1],id2);

	// frequency common between id1 and id2
	int freq = nodes[id1].N1[idVetex2].frequency;
	if(freq !=frequency)
		return 0;

	return 1;
}


//Return 1 if the frequency "frequency" is used between the nodes "id1" and "id2" for an active route
//Otherwise, returns 0.
int linkFrequencyRoute(int id1, int id2, int frequency)
{
    int condNode1 = 1,condNode2=1 ;

    // Verifier que le noeud id1 et id2 utilisent la fréquence 'frequency' pour communication
    condNode1 = linkUsedFrequency(id1,id2,frequency);

	//Test if the link is active (there is a route using it)
    if( (!linkIsActive(id1,id2)) && (!linkIsActive(id2,id1)) )
    	condNode2 = 0;

	return (condNode1*condNode2);
}//End of the function linkFrequency()


//Check if node i in N2 of node id used the given frequency or not. Return 0 if not, otherwise return the index of interface using it.
int usedfreqN2(int id, int i, int frequency)
{
    int neighbor2, j=0;

    if(i>=nodes[id].nbN2){
	fprintf(stderr,"Erreur usedfreqN2(): valeur du second argument incorrect\n");
	exit(1);
    }

    neighbor2=nodes[id].N2[i].id;
    for (j=0;j<nodes[i].nbOfRadios;j++)
    {
        if (nodes[neighbor2].frequency[j]==frequency) return j;
    }

    return -1;
}//End of the function usedfreqN2()

//Check if it exists a link (not on the common channel) between node id and it's 1-hop neiborgh with index i, return 1 if YES
int linkexist(int id,int i)
{
    int freq,id2;

	//index of the neighbor
	id2=nodes[id].N1[i].id;
	for (freq=1;freq<maxFreq;freq++)
		if (linkFrequency(id,id2,freq)) return(1);

    return 0;
}

//Check if exist the link (not common link) between node id and id2, return 1 if YES
int linkExist(int id,int id2)
{
    int freq;

	//index of the neighbor
	for (freq=1;freq<maxFreq;freq++)
		if (linkFrequency(id,id2,freq)) return(1);

    return 0;
}

//Check if exist the link (all the frequency) between node id and id2, return 1 if YES
int linkExist2(int id,int id2)
{
    int freq;

	for (freq=0;freq<maxFreq;freq++)
		if (linkFrequency(id,id2,freq)) return(1);

    return 0;
}

//Chek if node "id" has a free radio. Returns -1 if no.
//Returns the number of the first radio available if it exists.
int freeRadio(int id)
{
	int i;

	for(i=0;i<nodes[id].nbOfRadios;i++){
		if(nodes[id].frequency[i]==-1) return(i);
	}

	return(-1);
}

//Compute the conflict graph for a link.
int conflictGraphLink(int id1, int id2, int frequency)
{

    int i, j, idN1, idN2, conflict=0;

	//Two steps :
	//1; Add 1 for each link for links between id1 and nodes of N1 (of id1),
	//	 +1 for links between nodes in N1 (of id1) and nodes in N1 (of id1)
	//	 +1 for links between nodes in N1 (of id1) and nodes in N2 (of id2)
	//2; Add 1 for each links between nodes of N1 (of id2) and nodes of N2 (of id2) (but the last one must not belong to N2 of id1)
	// (all the neighborhood of id2 have been taken into account with N2 of id1).

	//step 1
	for(i=0;i<nodes[id1].nbN1;i++){
		idN1=nodes[id1].N1[i].id;//index of the neighbor

		//direct neighbor
		if(linkFrequency(id1,idN1,frequency)&&(idN1!=id2)){
			conflict++;
		}

		//2 neighbors together
		for(j=i+1;j<nodes[id1].nbN1;j++){
			if(linkFrequency(idN1,nodes[id1].N1[j].id,frequency)==1){
				conflict++;
			}
		}

		//neighbor with 2-neighbors
		for(j=0;j<nodes[id1].nbN2;j++){
			if(linkFrequency(idN1,nodes[id1].N2[j].id,frequency)==1){
				conflict++;
			}
		}

	}

	//step 2
	for(i=0;i<nodes[id2].nbN2;i++){
		idN2=nodes[id2].N2[i].id;//index of the 2-neighbor
		for(j=0;j<nodes[id2].nbN1;j++){
			idN1=nodes[id2].N1[j].id;//index of the neighbor
			//We verify that idN2 is not id1, not a neighbor or a 2-neighbor of id1, we add 1 if idN1 is neighbor of idN2
			if((idN1!=id1)&&(isNeighbor(id1,idN2)==0)&&(is2Neighbor(id1,idN2)==0)&&(linkFrequency(idN1,idN2,frequency)==1)){
				conflict ++;
			}
		}
	}

	return(conflict);

}//end of the function conflictGraphLink();

//Return the cardinal of the conflict graph in the 2-neighborhood for a given frequency.
//Only information of nodes[id] must be taken into account.
//It counts the conflict graph for all the links of node id.
//1. We compute the number of links of node id using the given frequency.
//2. We count the number of links using this frequency between the nodes of N1 and between the nodes of N1 and N2.
//The cardinality of the conflict graph is then  1*2 + 1^2.
int conflictGraphN2(int id, int frequency)
{
    int i, j, directLinks=0, noDirectLinks=0, conflict;

    //Firstly, check if node id used the given frequency or not. If not, the conlict graph is 0
    if(usedfreq(id,frequency)==-1) return 0;

    //Find all node in N1 that used the given frequency.
    for (i=0;i<nodes[id].nbN1;i++)
    {
         //Calculate the number of direct links of node id (link between id and it's 1-hop neighbor) using the given frequency
         if(usedfreqN1(id,i,frequency)!=-1) directLinks++;
    }


    //Count the number of links between nodes of N1 using the given frequency.
    for (i=0;i<nodes[id].nbN1;i++)
    {
    	//neighbor "i" used frequency
        if (usedfreqN1(id,i,frequency)!=-1)
        {
            for (j=i+1;j<nodes[id].nbN1;j++){
            	//is this neighbor is neighbor with i and uses the given frequency?
              if ((usedfreqN1(id,j,frequency)!=-1)&&(isNeighbor(nodes[id].N1[j].id,nodes[id].N1[i].id))) noDirectLinks++;
            }//end of for
        }//end of if
    }//end of for

    //The same in the 2-neighborhood. We are looking for links between N1 and N2 that use the given frequency.
    for (i=0;i<nodes[id].nbN2;i++)
    {
        if (usedfreqN2(id,i,frequency)!=-1)//The 2-neighbor "i" used the given frequency
	    //Count the number of links between "i" and N1(id) which used this frequency
            for (j=0;j<nodes[id].nbN1;j++)
                if ((usedfreqN1(id,j,frequency)!=-1)&&(isNeighbor(nodes[id].N2[i].id, nodes[id].N1[j].id))) noDirectLinks++;
    }

   conflict=directLinks*directLinks+directLinks*noDirectLinks; //total intererence equal to interference links of each multiple with number of direct links.
   return conflict;
}//end of the function conflictGraphN2();

//Return the cardinal of the conflict graph in the whole network.
//The argument is the first frequency we consider (=1 when we do not consider the common frequency -> frequency 0)
//it is 0 when we want the conflict graph for all the frequency.
int conflictGraph(int freqStart)
{
    	int j, k,id,linkID,freq,conflictGraph=0, nbOfLinks=0;
    	struct link links[MAX_LINK];

	if((freqStart!=0)&&(freqStart!=1)){
		fprintf(stderr,"conflictGraph(): Bad value of freqStart: must be 0 or 1 (=%d)\n",freqStart);
		exit(3);
	}

	for (freq=freqStart;freq<maxFreq;freq++)
    	{
        	//First, we construct the links set for frequency i
      		nbOfLinks=0;
		for (j=0;j<nbOfNodes;j++)
		{
           	 	if (usedfreq(j,freq)!=-1)//nodes j used frequency "freq"
               		{
				for (k=0;k<nodes[j].nbN1;k++)
               		  	{
                   			id=nodes[j].N1[k].id;
                   			if ((usedfreq(id,freq)!=-1)&&(nodes[j].id<id))
                      			{
                      				links[nbOfLinks].vertex1=nodes[j].id;
                      				links[nbOfLinks].vertex2=nodes[j].N1[k].id;
                      				nbOfLinks++;
                      			}
                   		}
               		}
            	}//End of contructing the links set for frequency i

		//Calculate the total interference for frequency freq
		//For each link, we compute and sum the conflict graph
        	for (linkID=0;linkID<nbOfLinks;linkID++)
            	{
            		for (k=linkID+1;k<nbOfLinks;k++)
                	{
				//For each link "linkID", we look if there is a link "k" in N1 or N2 w.r.t. "linkID"

				//Is "k" in N1 w.r.t. "linkID"? (if yes one of the vertex is in common)
                		if ((links[k].vertex1==links[linkID].vertex1)||(links[k].vertex1==links[linkID].vertex2)||(links[k].vertex2==links[linkID].vertex2)) conflictGraph++;
				//Do they have a common a neighbor? (yes if one of the vertex is neighbor with one of the other).
				else if ((isNeighbor(links[k].vertex1,links[linkID].vertex1))||(isNeighbor(links[k].vertex1,links[linkID].vertex2))||(isNeighbor(links[k].vertex2,links[linkID].vertex1))||(isNeighbor(links[k].vertex2,links[linkID].vertex2))) conflictGraph++;
                	}
            	}

       	}
    	return conflictGraph;
}//End of the function conlictGraph()

//Return the cardinal of the conflict graph in the whole network.
//The argument is the first frequency we consider (=1 when we do not consider the common frequency -> frequency 0)
//it is 0 when we want the conflict graph for all the frequency.
//The difference with the function above is that we count the total number of links (even if it corresponds to the same pair of neighbors).
int conflictGraphGreedy(int freqStart)
{
    int j, k,id,linkID,freq,radio,radio2,conflictGraph=0, nbOfLinks=0;
    struct link links[MAX_LINK];

	if((freqStart!=0)&&(freqStart!=1))
	{
		fprintf(stderr,"conflictGraph(): Bad value of freqStart: must be 0 or 1 (=%d)\n",freqStart);
		exit(3);
	}

	for (freq=freqStart;freq<maxFreq;freq++)
   	{
        //First, we construct the links set for frequency i
      	nbOfLinks=0;
		for (j=0;j<nbOfNodes;j++)
		{
			for(radio=0;radio<nbOfRadios;radio++)
			{
           	 		if (nodes[j].frequency[radio]==freq)//nodes j used frequency "freq" on radio "radio"
           			{
							for (k=0;k<nodes[j].nbN1;k++)
							{
								id=nodes[j].N1[k].id;
								for(radio2=0;radio2<nbOfRadios;radio2++)
								{
									if ((nodes[j].id<id)&&(nodes[id].frequency[radio2]==freq))
									{
										links[nbOfLinks].vertex1=nodes[j].id;
										links[nbOfLinks].vertex2=nodes[j].N1[k].id;
										nbOfLinks++;

										if(nbOfLinks>=MAX_LINK)
										{
											fprintf(stderr,"Erreur conflictGraphGreedy(): depassement de tableau\n");
											exit(2);
										}
									}

								}
							}
           			}
			}
      }//End of contructing the links set for frequency i

		//Calculate the total interference for frequency freq
		//For each link, we compute and sum the conflict graph
        	for (linkID=0;linkID<nbOfLinks;linkID++)
            	{
            		for (k=linkID+1;k<nbOfLinks;k++)
                	{
				//For each link "linkID", we look if there is a link "k" in N1 or N2 w.r.t. "linkID"

				//Is "k" in N1 w.r.t. "linkID"? (if yes one of the vertex is in common)
                		if ((links[k].vertex1==links[linkID].vertex1)||(links[k].vertex1==links[linkID].vertex2)||(links[k].vertex2==links[linkID].vertex2)||(links[k].vertex2==links[linkID].vertex1))
                			conflictGraph++;
				//Do they have a common a neighbor? (yes if one of the vertex is neighbor with one of the other).
				else if ((isNeighbor(links[k].vertex1,links[linkID].vertex1))||(isNeighbor(links[k].vertex1,links[linkID].vertex2))||(isNeighbor(links[k].vertex2,links[linkID].vertex1))||(isNeighbor(links[k].vertex2,links[linkID].vertex2)))
						conflictGraph++;
                	}
            	}

       	}
    	return conflictGraph;
}//End of the function conlictGraphGreedy()



//Return the cardinal of the conflict graph in the whole network.
//We does count the conflict graph only on the common frequency (frequency 0)
int conflictGraphCommonChannel()
{
    	int j, k,id,linkID,conflictGraph=0, nbOfLinks=0;
    	struct link links[MAX_LINK];

       	//First, we construct the links set for frequency i
      	nbOfLinks=0;
	for (j=0;j<nbOfNodes;j++)
	{
		for (k=0;k<nodes[j].nbN1;k++)
                {
                	id=nodes[j].N1[k].id;
                  	if (nodes[j].id<id)
                      	{
                      		links[nbOfLinks].vertex1=nodes[j].id;
                      		links[nbOfLinks].vertex2=nodes[j].N1[k].id;
                      		nbOfLinks++;
                      	}
		}
	}//End of contructing the links set for frequency i

	//Calculate the total interference on the common channel
	//For each link, we compute and sum the conflict graph
       	for (linkID=0;linkID<nbOfLinks;linkID++)
	{
		for (k=linkID+1;k<nbOfLinks;k++)
		{
			//For each link "linkID", we look if there is a link "k" in N1 or N2 w.r.t. "linkID"
			//Is "k" in N1 w.r.t. "linkID"? (if yes one of the vertex is in common)
                	if ((links[k].vertex1==links[linkID].vertex1)||(links[k].vertex1==links[linkID].vertex2)||(links[k].vertex2==links[linkID].vertex2)) conflictGraph++;
			//Do they have a common a neighbor? (yes if one of the vertex is neighbor with one of the other).
			else if ((isNeighbor(links[k].vertex1,links[linkID].vertex1))||(isNeighbor(links[k].vertex1,links[linkID].vertex2))||(isNeighbor(links[k].vertex2,links[linkID].vertex1))||(isNeighbor(links[k].vertex2,links[linkID].vertex2))) conflictGraph++;
               	}
	}

    	return conflictGraph;
}//End of the function conlictGraphCommonChannel()



int nodeMaxCostMinHops(struct tableEntry* table, int size)
{
	int i, best=-1, nbOfHops=0;
	float max=0.0;


	for(i=0;i<size;i++)
	{
		//We find a path with a better cost (greater cost)
		if( (table[i].done==0) && (table[i].minMetricPath>max) )
		{
			best=i;
			max=table[i].minMetricPath;
			nbOfHops=table[i].nbOfHops;
		}

		//We find a path with the same cost, but the number of hops is less
		if( (table[i].done==0) && (table[i].minMetricPath==max) && (table[i].nbOfHops<nbOfHops) )
		{
			best=i;
			max=table[i].minMetricPath;
			nbOfHops=table[i].nbOfHops;
		}
	}

	//may return -1
	return(best);
}//end of fct nodeMaxCostMinHops()


//Compute the routing table of node nodeId.
//We use a modified version of the Dijkstra algorithm. The cost is the min of the metric on the path (field in the info-neighbor structure).
//When two paths have the same costs, we choose the one with the smallest number of hops.
//disjointPaths indicates if we can have several routes (disjointPaths=0) or only one route (disjointPaths=1) per node.
//The malloc/free for this table must be done in the call function.
void updateTableEntry(struct tableEntry *table, int nodeId)
{
	int i, currentNode, idNeighbor, cost;

	//We initialize the table
	for(i=0;i<nbOfNodes;i++)
	{
		table[i].id=i;
		table[i].done=0;
		table[i].minMetricPath=0;
		table[i].nbOfHops=0;
		table[i].nextHop=-1;
		table[i].prevHop=-1;
	}

	//Update the route to the node itself.
	table[nodeId].minMetricPath=99999999;

	//While the table is not empty (empty = all the "done" fields are equal to 1)
	//currentNode is the node with the best cost in the table
	while((currentNode=nodeMaxCostMinHops( table, nbOfNodes))>=0)
	{
		table[currentNode].done=1;

		//We update the table for the currentNode's neighbors
		for(i=0;i<nodes[currentNode].nbN1;i++)
		{
			idNeighbor=nodes[currentNode].N1[i].id;
			if( (table[idNeighbor].done==0) && (nodes[idNeighbor].routeFlag==0))
			{
				//The new cost to reach idNeighbor is the min to reach currentNode and the link (currentNode,idNeighbor)
				cost = MIN(table[currentNode].minMetricPath,nodes[currentNode].N1[i].metric);

				//If this cost is better (greater) or equal but with a smaller number of hops, we update the entry for idNeighbor
				if(cost>table[idNeighbor].minMetricPath || ( (cost==table[idNeighbor].minMetricPath) && (table[idNeighbor].nbOfHops > table[currentNode].nbOfHops+1) ))
				{
					table[idNeighbor].minMetricPath=cost;
					table[idNeighbor].nbOfHops=table[currentNode].nbOfHops+1;

					if(table[idNeighbor].nbOfHops==1) table[idNeighbor].nextHop=idNeighbor;
					else table[idNeighbor].nextHop=table[currentNode].nextHop;
					table[idNeighbor].prevHop=currentNode;
				}
			}
		}
	}//end of while()
}//end of fct updateTableEntry()

//Compute the routing table of node id.
//We use a modified version of the Dijkstra algorithm. The cost is the min of the metric on the path (field in the info-neighbor structure).
//When two paths have the same costs, we choose the one with the smallest number of hops.
void updateRoutingTableDijsktra(int id)
{
	int i;
	struct tableEntry* table;//The struct definition is in type.h


	//Ressource allocation for the two arrays Nk and listNodes
	table=(struct tableEntry *) malloc(nbOfNodes*sizeof(struct tableEntry));

	//The best paths is computed here, and is stored in the table.
	updateTableEntry(table, id);

	//The job is done. Now, we update the routing table entries.
	fprintf(stderr,"--DEBUG-- Routing entries node %d ----- \n",id);
	for(i=0;i<nbOfNodes;i++)
	{
		if(i==id)
		{
			nodes[id].routingTable[i].destination=i;
			nodes[id].routingTable[i].nextHop=i;
		}//if

		if(i!=id)
		{
			nodes[id].routingTable[i].destination=i;
			nodes[id].routingTable[i].nextHop=table[i].nextHop;
			nodes[id].routingTable[i].cost=table[i].minMetricPath;
		}//if
	}

	free(table);
}//end of function updateRoutingTableDijsktra()

//Compute the routing table of node id but for a specific destination.
//We use a modified version of the Dijkstra algorithm. The cost is the min of the metric on the path (field in the info-neighbor structure).
//When two paths have the same costs, we choose the one with the smallest number of hops.
//routeNumber is the route number (remember that we may have several routes).
//Warning: We substract the path cost to the metric along this path - to indicate that this resource is not available anymore (when computing multi-path to the same destination).
int updateRouteSourceDestination(int source, int destination, int routeNumber)
{
	int next, prev, cost, index;
//	int disjointPaths=0;//If 1 there is only one route per node - If 0 we may have several routes using the same node

	struct tableEntry* table;//The struct definition is in type.h

	//Ressource allocation for the table
	table=(struct tableEntry *) malloc(nbOfNodes*sizeof(struct tableEntry));

	//The best paths is computed here, and is stored in the table.
	updateTableEntry(table, source);

	//The job is done. Now, we update the routing table entries.
	//We start from the destination and update the node's table on the path.
	fprintf(stderr,"--DEBUG-- Routing entries %d node %d ----- \n",routeNumber,source);


	//No route
	if(table[destination].nextHop==-1) return(-1);

	//There is a route
	cost=table[destination].minMetricPath;//Set path cost
	prev=table[destination].prevHop;
	next=destination;
	while(prev!=-1)
	{
		fprintf(stderr,"   --DEBUG-- %d --> %d Bi=%d\n",prev,next,getMetric(prev,next));

		nodes[prev].routingTable[routeNumber].destination=destination;
		nodes[prev].routingTable[routeNumber].nextHop=next;
		nodes[prev].routingTable[routeNumber].cost=table[next].minMetricPath;//almost true

		//We substract the cost of the route to the metric (on the biderictional link prev-->next and next-->prev)
		index=getIndexN1(nodes[prev],next);//Index of "next" in the neighborhood of "prev" (table N1 of the struct node)
		nodes[prev].N1[index].metric=nodes[prev].N1[index].metric-cost;
		index=getIndexN1(nodes[next],prev);
		nodes[next].N1[index].metric=nodes[next].N1[index].metric-cost;


		// Global variable: disjointPaths
		// If 1 there is only one route per node
		// If 0 we may have several routes using the same node
		if( (disjointPaths == 1) &&(prev >= 0) && (prev != source) && (prev != destination))
		{
			nodes[prev].routeFlag = 1;
		}


		next=prev;
		prev=table[prev].prevHop;
		//fprintf(stderr,"   --DEBUG-- after %d --> %d\n",prev,next);
	}


	free(table);

	return(0);
}//end of function updateRoutingTableDijsktra()

